public class Test {
    public static void main(String[] args) {
        testKMP();
    }
    public static void testKMP() {
        //主串
        String s1 = "aabaabaaf";
        //模式串
        String s2 = "aabaaf";
        //构建next数组
        int[] next = new int[s2.length()];
        //初始化next
        /*for (int i = 0; i < next.length; i++) {
            next[i] = 0;
        }*/
        next[0] = 0;
        createNext(next, s2);
        for (int i = 0; i < next.length; i++) {
            System.out.print(next[i] + " ");
        }
    }

    public static void createNext(int[] next, String s2) {
        //定义两个下标，一个在前一个在后
        int i = 0, j = 0;
        for (j = 1; j < s2.length(); j++) {
            //只有先考虑不匹配的情况才能使next数组正确
            while (i > 0 && s2.charAt(i) != s2.charAt(j)) {
                i = next[i - 1];
            }
            if (s2.charAt(i) == s2.charAt(j)) {
                i++;
            }
            next[j] = i;
        }
    }

    public static void main1(String[] args) {
        String s = "abcde";
        System.out.println(s.length());
        System.out.println(s.substring(1 + 1));
        s = s + "fg";
        System.out.println(s.length());
    }
    public static boolean isValid() {
        return false;
    }
}
